/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/coin-change
   @Language: C++
   @Datetime: 19-06-04 14:07
   */


// Method 1, DP, Time O(n*k), Space O(k), Time 101ms
class Solution {
public:
	/**
	 * @param coins: a list of integer
	 * @param amount: a total amount of money amount
	 * @return: the fewest number of coins that you need to make up
	 */
	int coinChange(vector<int> &coins, int amount) {
		// write your code here
		if(amount==0) return 0;
		vector<int> dp(amount+1,INT_MAX);
		for(int i=0; i<=amount; ++i){
			for(int j=0; j<coins.size(); ++j){
				if(i==coins[j]) dp[i]=1;
				if(i>coins[j] && dp[i-coins[j]]!=INT_MAX)
					dp[i]=min(dp[i],dp[i-coins[j]]+1);
			}
		}
		return dp[amount]==INT_MAX?-1:dp[amount];
	}
};

// Method 2, Time O(n*k), Space O(k), Time 101ms
class Solution {
	int dfs(vector<int> &coins, int amount, vector<int> &dp){
		if(amount<0) return -1;
		if(dp[amount]!=INT_MAX) return dp[amount];
		for(int i=0; i<coins.size(); ++i){
			if(coins[i]==0) continue;
			const int n=dfs(coins,amount-coins[i],dp);
			if(n>=0) dp[amount]=min(dp[amount],n+1);
		}
		if(dp[amount]==INT_MAX) dp[amount]=-1;
		return dp[amount];
	}
public:
	/**
	 * @param coins: a list of integer
	 * @param amount: a total amount of money amount
	 * @return: the fewest number of coins that you need to make up
	 */
	int coinChange(vector<int> &coins, int amount) {
		// write your code here
		vector<int> dp(amount+1,INT_MAX);
		dp[0]=0;
		return dfs(coins,amount,dp);
	}
};
